#include <iostream>
#include <list>
#include <vector>
#include <deque>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int i)
    {
        left = NULL;
        right = NULL;
        val = i;
    }
};

// class Solution
// {
// public:
//     /**
//      * 
//      * @param root TreeNode类 
//      * @return int整型vector<vector<>>
//      */
//     vector<vector<int>> levelOrder(TreeNode *root)
//     {
//         if (root == NULL) {
//             return vector<vector<int>>();
//         }
//         vector<TreeNode *> list;
//         vector<vector<int>> result;
//         int last_cnt = 0;
//         list.push_back(root);
//         if (root->left != NULL)
//         {
//             list.push_back(root->left);
//             last_cnt++;
//         }

//         if (root->right != NULL)
//         {
//             list.push_back(root->right);
//             last_cnt++;
//         }
//         vector<int> r0;
//         r0.push_back(root->val);
//         result.push_back(r0);
//         int i = 1;
//         while (i < list.size())
//         {
//             vector<int> r;
//             int tmp = last_cnt;
//             last_cnt = 0;
//             if (tmp == 0)
//             {
//                 i++;
//                 continue;
//             }
//             for (int j = 0; j < tmp; j++)
//             {
//                 TreeNode *root = list[i];
//                 r.push_back(root->val);

//                 if (root->left != NULL)
//                 {
//                     list.push_back(root->left);
//                     last_cnt++;
//                 }

//                 if (root->right != NULL)
//                 {
//                     list.push_back(root->right);
//                     last_cnt++;
//                 }
//                 i++;
//             }
//             result.push_back(r);
//         }
//         return result;
//     }
// };


/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        if(root == NULL) 
            return {};
        deque<TreeNode*> de;// 广度优先借助的队列
        de.push_back(root);
        vector<vector<int> > v; // 当前层次的节点数
        vector<int> v1;
        int count = 1;
        int loop = 0;
        while(de.size())
        {
            TreeNode* node = de.front();
            v1.push_back(node->val);
            if(node->left)
            {
                ++loop;
                de.push_back(node->left); 
            }
               
            if(node->right)
            {
                ++loop;
                de.push_back(node->right);
            }
                
            de.pop_front();
            --count;
            if(count == 0)
            {
                count = loop;
                loop = 0;
                v.push_back(v1);
                vector<int> v2;
                v1 = v2;
            }
        }
        return v;
    }
};


int main()
{
    Solution so;
    TreeNode *root = new TreeNode(3);
    TreeNode *l1 = new TreeNode(9);
    TreeNode *r1 = new TreeNode(20);
    TreeNode *l2 = new TreeNode(15);
    TreeNode *r2 = new TreeNode(7);
    root->left = l1;
    l1->left = l2;
    l2->left = r1;
    r1->left = r2;
    // root->right = r1;
    // r1->left = l2;
    // r1->right = r2;
    vector<vector<int>> v = so.levelOrder(NULL);
    cout << v.size() << endl;
    delete root, l1, l2, r1, r2;
    return 0;
}